// https://leetcode.cn/problems/subarray-sums-divisible-by-k/

// 题干：给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
//       子数组 是数组的 连续 部分。

// 示例：输入：nums = [4,5,0,-2,-3,1], k = 5
//       输出：7

// 碎语：同和为k的子串一样，但是本题需要考虑C++余数的负数处理

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        int sum = 0, ret = 0;
        unordered_map<int, int> hash;
        hash[0] = 1;

        for (const auto& num : nums){
            sum += num; // 计算当前前缀和

            // 判断当前有多少个前缀和的余数符合条件
            if (hash.count((sum % k + k) % k)) ret += hash[(sum % k + k) % k];

            // 存下当前的前缀和余数
            hash[(sum % k + k) % k]++;
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {4,5,0,-2,-3,1};

    cout << sol.subarraysDivByK(nums, 5) << endl;
    
    return 0;
}